package src.java.medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution15 {
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int i = 0, j = i + 1, k = nums.length - 1;
        List<List<Integer>> result = new ArrayList<>();
        while (i < nums.length - 2 && nums[i] <= 0) {
            while (j < k && k < nums.length) {
                if (nums[i] + nums[j] + nums[k] == 0) {
                    result.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    j = moveRight(nums, j);
                    k = moveLeft(nums, k);
                } else if (nums[i] + nums[j] + nums[k] < 0) {
                    j = moveRight(nums, j);
                } else {
                    k = moveLeft(nums, k);
                }
            }
            i = moveRight(nums, i);
            j = i + 1;
            k = nums.length - 1;
        }
        return result;
    }

    private static int moveLeft(int[] nums, int i) {
        int index = i - 1;
        while (index >= 0 && nums[index] == nums[i]) {
            index--;
        }
        return index;
    }

    private static int moveRight(int[] nums, int i) {
        int index = i + 1;
        while (index < nums.length && nums[index] == nums[i]) {
            index++;
        }
        return index;
    }

    public static void main(String[] args) {
        int[] nums = {0,-4,-1,-4,-2,-3,2};
        List<List<Integer>> result = threeSum(nums);
        System.out.println(result);
    }
}
